package vj.recursion;

import java.util.ArrayList;
import java.util.Random;

public class CountPossibleSums {
	
	//public CntPossbleSum(int )
	
	public static void main(String[] args) {
		int a[] = new int[30];
		for(int i = 0; i < a.length; i++) {
			a[i] = i;
		}
		shuffle(a);
	
		int b[] = new int[]{1, 2, 5, 10};
		ArrayList<Integer> l = new ArrayList<Integer>();
		//CntPossbleSum.recCnt(b, l, 4, 0);
		ArrayList<Integer> l1 = new ArrayList<Integer>();
		CountPossibleSums.NumSum(7, l1, 1, 0);
		
		System.out.println(CountPossibleSums.NumSumCnt(7, l1, 1, 0));
		
		
		//CntPossbleSum.count1(a, 57);
		//System.out.println(CntPossbleSum.count2(a, 1345));
		//CntPossbleSum.recCnt(a, 5, 2);
		//System.out.println(printTriplets(a));
		
	}
	
	private static void shuffle(int[] a) {
		Random r = new Random();
		int m, temp;
		for(int j = 0; j < a.length; j++) {
			m = r.nextInt(29);
			temp = a[m];
			a[m] = a[j];
			a[j] = temp;
		}
	}

	public static int printTriplets(int a[]) {
		int triplets = 0;
		for(int i = 0; i < a.length - 2; i++) {
			for(int j = i + 1; j < a.length - 1; j++) {
				for(int k = j + 1; k < a.length; k++) {
					System.out.println("(" + a[i] + "," + a[j] + "," + a[k] + ")");
					triplets++;
				}
 			}
		}
		return triplets;
	}
	
	public static int count(int a[], int N) {
		
		int cnt = 0;
		
		for(int i = 0 ; 1 * i <= N; i++) {
			/*if(1*i == N)
				cnt++;*/
			for(int j = 0; (2 * j) + (i * 1) <= N; j++) {
				if((2 * j) + i == N) {
					cnt++;
					for(int k = 0; k < i; k++)
						System.out.print(" 1 ");
					for(int k = 0; k < j; k++)
						System.out.print(" 2 ");
					System.out.println("");
				}
			}
		}
		System.out.println(cnt);
		return cnt;
	}

	public static int count1(int a[], int N) {
		
		int cnt = 0;
		
		for(int i = 0 ; 1 * i <= N; i++) {
			for(int j = 0; (2 * j) + (i * 1) <= N; j++) {
				for(int m = 0; (m * 4) + (2 * j) + (i * 1) <= N; m++) {
					if((4 * m) + (2 * j) + i == N) {
						cnt++;
						for(int k = 0; k < i; k++)
							System.out.print(" 1 ");
						for(int k = 0; k < j; k++)
							System.out.print(" 2 ");
						for(int k = 0; k < m; k++)
							System.out.print(" 4 ");
						System.out.println("");
					}
				}
			}
		}
		System.out.println(cnt);
		return cnt;
	}
	
	public static int count2(int a[], int N) {
		
		int cnt = 0;
		
		for(int i = 0 ; 1 * i <= N; i++) {
			for(int j = 0; (2 * j) + (i * 1) <= N; j++) {
				for(int m = 0; (m * 4) + (2 * j) + (i * 1) <= N; m++) {
					if((4 * m) + (2 * j) + i == N) {
						cnt++;
					}
				}
			}
		}
		//System.out.println(cnt);
		return cnt;
	}
 
 /* public static int count3(int a[], int N, int k) {
		
	while(a[k] <= N) {
		if(a[k] == N)
	}
	  	
	  
	}*/
  
  /*
   * n is the number of elements taken from the array to form the target sum
   * n = 1 means we check is to possible to reach target sum by using a single element any number of times.
   * n  = 2 means  we check is to possible to reach target sum by using two elements any number of times.
   */
  
  public static void recCnt(int a[], ArrayList<Integer> n, int sum, int pSum) {
	  if(sum == pSum) {
		  for(Integer i : n)
			  System.out.print( i + " + ");
		  System.out.println();
		  return;
	  }
	  for(int i = 0; i < a.length; i++) {
		  if(pSum + a[i] <= sum) {
			  n.add(a[i]);
			  recCnt(a, n, sum, pSum + a[i]);
			  n.remove(new Integer(a[i]));
		  }
	  }
	  
  }

  
  public static void NumSum(int targetSum, ArrayList<Integer> v, int startVal, int partialSum)   {
       if (partialSum == targetSum)
       {
    	   System.out.print( "{");
          for (int i=0; i < v.size(); i++)
          {
        	  System.out.print(" " + v.get(i));
          } 
          System.out.print( "}\n" );
          return;
       }
       for (int i = startVal; i < targetSum;i++)
       { 
            if (i+partialSum <= targetSum)
            {
            	v.add(i);
               NumSum(targetSum, v, i, partialSum+i);
               v.remove(new Integer(i));
            }
       }
  }
  
  public static int NumSumCnt(int targetSum, ArrayList<Integer> v, int startVal, int partialSum)   {
      if (partialSum == targetSum)
      {
   	   /*System.out.print( "{");
         for (int i=0; i < v.size(); i++)
         {
       	  System.out.print(" " + v.get(i));
         } 
         System.out.print( "}\n" );*/
         return 1;
      }
      int cnt = 0;
      for (int i = startVal; i < targetSum;i++)
      { 
           if (i+partialSum <= targetSum)
           {
        	   
           	v.add(i);
           	cnt+= NumSumCnt(targetSum, v, i, partialSum+i);
              v.remove(new Integer(i));
           }
      }
      return cnt;
 }

  

	
}
